package q378_kthSmallest;

public class Solution {
    /*
     此题完全可以参考第668题 在乘法表中寻找第k小的数
     唯一的不同在于将其中判断小于mid的数字有多少进行抽取获得了一个函数
     */
    public int kthSmallest(int[][] matrix, int k) {
        int l = matrix[0][0], r = matrix[matrix.length - 1][matrix.length - 1];
        while (l < r) {

            int mid = l + ((r - l) >> 1);
            if (check(matrix, mid, k)) {
                r = mid;
            }else {

                l = mid + 1;
            }
        }
        // 最后返回到左侧
        return l;
    }
    public boolean check(int[][] matrix, int mid, int k) {
        // 从左下角开始找
        int i = matrix.length - 1, j = 0;
        int countLower = 0;
        while (i >= 0 && j < matrix.length) {
            if (matrix[i][j] <= mid) {
                // 这里加的是一列中有多少小于mid的数字
                countLower += i + 1;
                j++;
            }else {
                i--;
            }
        }

        return countLower >= k;
    }

}
